
// 494.目标和
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        // 数组和为sum  ,要在数组中挑选一些+ , 挑选一些数 - 
        // 设加的数和为 a  , 减的数绝对值和为b : a - b = target , a + b =sum 
        // 得到 a = (target + sum )/2 ;
        // 所以就是在数组中选择一些数 , 这些数相加为 (target + sum )/2 
        // 使用背包DP

        int n = nums.size();
        int sum = accumulate(nums.begin() , nums.end() ,0);
        
        int aim = (target + sum )/2 ;
        if((target + sum)%2 == 1 || aim < 0) return 0;

        vector<int> dp(aim + 1);
        dp[0] = 1;
        for(int i = 1 ; i <= n ; i++)
        {
            for(int j = aim ; j >= nums[i - 1] ; j--)
                if(j - nums[i - 1] >= 0) dp[j] += dp[j - nums[i - 1]];
        }
        return dp[aim];
    }
};